import java.util.ArrayList;

public class LeetCode93 {
    public static void main(String[] args) {
        String s = "25525511135";
//        String s = "0279245587303";
        Solution solution = new Solution();
        System.out.println(solution.restoreIpAddresses(s));
    }
}

class Solution {
    ArrayList<String> list = null;

    public ArrayList<String> restoreIpAddresses(String s) {
        list = new ArrayList<>();
        createString(s.toCharArray(), 0, new int[4], 0);
        return list;
    }

    public void createString(char[] ch, int index, int[] res, int resIndex) {

        if (resIndex == 4 && index == ch.length) {
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < 3; i++) {
                stringBuilder.append(res[i]);
                stringBuilder.append('.');
            }
            stringBuilder.append(res[3]);
            list.add(stringBuilder.toString());
            return;
        }
        if (resIndex < 4 && index == ch.length || resIndex == 4 && index < ch.length) {
            return;
        }
        int temp = ch[index] - '0';
        res[resIndex] = temp;
        createString(ch, index + 1, res, resIndex + 1);
        if (temp != 0) {
            for (int i = 1; i < 3 && index + i < ch.length; i++) {
                temp = temp * 10 + ch[index + i] - '0';
                if (temp > 0 && temp < 256) {
                    res[resIndex] = temp;
                    createString(ch, index + i + 1, res, resIndex + 1);
                } else {
                    break;
                }
            }
        }
    }
}
